package com.zhj.algorithm.sort;

/**
 * @PackageName:com.zhj.algorithm.sort
 * @ClassName:Selection
 * @auter: 朱慧杰
 * @date:2020/7/17 0017 8:33
 **/
public class SelectionSort {

    public static void selectSort(Integer[] arr) {
        for (int i = 0; i < arr.length-1; i++) {
            int minIndex = i;
            for (int j = i+1; j < arr.length; j++) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            if (i != minIndex) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

    /**
     * 对数组a中的元素排序  ----选择排序
     * @param a
     */
    public static void sort (Comparable[] a) {

        for(int i = 0; i < a.length - 1; i++) {
            // 定义一个变量 保存最小值 默认为第一个
            int minIndex = i;

            for (int j = i + 1; j < a.length; j++) {
                // 比较最小索引与j索引所在位置
                // 时间复杂度 O(n^2)
                if(greater(a[minIndex] , a[j])) {
                    minIndex = j;
                }
            }

            // 交换最小元素所在索引minIndex处的值和索引i处的值
            exch(a, i, minIndex);

        }

    }

    /**
     * 比较v元素是否大于m元素
     * @param a
     */
    public static boolean greater (Comparable v, Comparable w) {
        return v.compareTo(w)>0;
    }

    /**
     * 数组元素i 和 j 交换位置
     * @param a
     */
    public static void exch (Comparable[] a, int i, int j) {

        Comparable temp;

        temp = a[i];
        a[i] = a[j];
        a[j] = temp;

    }

}
